package simple.array;

/**
 * <a href="https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/">1287. 有序数组中出现次数超过25%的元素</a>
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
 * 请你找到并返回这个整数
 * 示例：
 *   输入：arr = [1,2,2,6,6,6,6,7,10]
 *   输出：6
 * 提示：
 *   1 <= arr.length <= 10^4
 *   0 <= arr[i] <= 10^5
 * @author 刘学松
 * @date 2023-07-31 15:01
 */
public class 有序数组中出现次数超过百分之25的元素 {
    public static void main(String[] args) {
        findSpecialInteger(new int[]{0, 0, 2, 2, 2, 4, 4, 4, 6, 6, 10, 10, 10, 10, 10, 12, 14, 16, 16});
    }
    public static int findSpecialInteger(int[] arr) {
        int step = arr.length / 4;
        int index = step;
        int length = getLength(arr, index);
        while (length <= step) {
            index += step;
            length = getLength(arr, index);
        }
        return arr[index];
    }

    public static int getLength(int[] arr, int index) {
        int val = arr[index];
        int left = index, right = index;
        while (left >= 0 && arr[left] == val) {
            --left;
        }
        while (right < arr.length && arr[right] == val) {
            ++right;
        }
        return right - left - 1;
    }
}
